﻿#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    // 474. 一和零
    /*int findMaxForm(vector<string>& strs, int m, int n)
    {
        int len = strs.size();
        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));

        for (int i = 1; i <= len; i++)
        {
            int a = 0, b = 0;
            for (auto ch : strs[i - 1])
                if (ch == '0')
                    a++;
                else
                    b++;
            for (int j = 0; j <= m; j++)
            {
                for (int k = 0; k <= n; k++)
                {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= a && k >= b)
                        dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1);
                }
            }
        }
        return dp[len][m][n];
    }*/

    int findMaxForm(vector<string>& strs, int m, int n)
    {
        int len = strs.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        for (int i = 1; i <= len; i++)
        {
            int a = 0, b = 0;
            for (auto ch : strs[i - 1])
                if (ch == '0')
                    a++;
                else
                    b++;
            for (int j = m; j >= a; j--)
                for (int k = n; k >= b; k--)
                    dp[j][k] = max(dp[j][k], dp[j - a][k - b] + 1);
        }
        return dp[m][n];
    }
};

int main()
{
    vector<string> v{ "10", "0001", "111001", "1", "0" };
    cout << Solution().findMaxForm(v, 5, 3) << endl;

    return 0;
}